// 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。
// 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

// 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。


const maxEnvelopes = function (envelopes: number[][]): number {
    // 边界情况
    if (envelopes.length < 1) {
        return 0;
    }
    // 先对信封进行二维排序
    envelopes.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    // 初始化DP数组，DP[i]表示以第i项元素作为结尾的最长序列
    const dp: number[] = new Array(envelopes.length).fill(1);
    // 双重循环，i表示当前元素，j表示当前元素之前的所有元素 
    for (let i = 0; i < envelopes.length; i++) {
        for (let j = 0; j < i; j++) {
            const currEnvelope: number[] = envelopes[i];
            // 长和宽都需要严格大于
            if (currEnvelope[0] > envelopes[j][0] && currEnvelope[1] > envelopes[j][1]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
    }
    return Math.max(...dp);
};


// 这道题目也是一道比较典型的可以根据模板套路解决，只是比较难想到
// 首先翻译知道题目，需要想到这道题目本质上是：
// 找出二维数组的一个排列，使得其中有最长的单调递增子序列（即两个维度都严格递增）。
// 如果想不到这层抽象，难度则会加大...
// 之后既然是找最长递增序列，那么可以想到需要对原数组进行一层排序
// 排序的意义是降低数组的混乱度（直接遍历会存在大量边缘情况），同时它可以保证：
// 遍历到当前元素时，当前元素之前的所有元素都是起码存在长是小于当前元素的长（但宽则不能保证），即不一定能装
// 之后声明一个DP数组，DP的每一项表示以该项对应元素作为结尾的最长序列长度
// 再双重循环遍历当前元素i前的每一项，让DP[i]在DP[j] + 1和DP[i]中做决策，舍弃小者
// 双重循环完成后，线性扫描dp数组即可得到最后的结果。
